1. Field of Invention
This invention relates to the communication mechanism within parallel computer systems.
2. Description of Prior Art
Many topologies have been proposed and constructed for interconnecting sets of computers as a combined parallel resource available to a single task, or application. Meshes and hypercubes have seen very widespread use as exemplified by the Intel Paragon, the Thinking Machines Connection Machine, the Maspar, and many earlier machines. The simple structure of a ring has been employed in architectures such as the iWarp machine (Intel) and RAP (International Computer Science Institute), for support of at least some of the inter-processor communication. Local area networks (LAN) have also seen applications of ring topologies, e.g. the IBM Token Ring, and the Cambridge Fast Ring (Cambridge University).
More recently, the Scalable Coherent Interface (SCI) employs a ring as a multiprocessor interconnect. U.S. Pat. No. 5,119,481 [Frank, et al, Jun. 2, 1992] describes another ring interconnect, employing point-to-point transfers. Neither of these interconnects, however, support either bidirectional or systolic transfers, two essential components of this disclosure. Nor do these schemes provide a centralized traffic scheduler, pivotal here in achieving systolic data transfers. Finally, neither of these approaches, nor any of those cited above, support the types of systolic data transfers detailed in this disclosure.
While it is clear to parallel computer architects that a ring affords a simple means of interconnecting a potentially large number of processors, the problems of scheduling, contention, and blocking appear to pose serious obstacles to a contemporary ring-based architectures. Without a strategy to deal with these issues, a ring serves principally to translate a common bus into a high-speed pipelined version of the same thing. Though there are benefits to be had even there, they represent only a fraction of the actual potential.
The invention disclosed herein presents an efficient and novel scheme for achieving a higher degree of ring bandwidth utilization than has hitherto been possible. Within a centrally controlled framework, a versatile combination of statically and dynamically routed data communication is provided. A technique, or strategy, for maximizing network bandwidth is elaborated. These objects are achieved by employing some existing techniques, available in the art, as well as introducing some new ones. The utility of this invention will be demonstrated in several important applications, from the areas of Fourier analysis, partial differential equations, and pattern recognition.